package sorter;

/**
 * 快速排序：将某个元素放置到最终位置，再递归地对左右子序列应用快速排序。
 * 时间复杂度：O(nlog(n))
 * 稳定性：并非元素两两比较交换，因此不稳定
 * @author Zhang Ziyi
 */
public class QuickSorter implements Sorter{
    @Override
    public void sort(int[] arr) {
        quickSort(arr, 0, arr.length);
    }

    /**
     * 快速排序
     * @param arr 排序数组
     * @param startInclusive 起始下标(包含)
     * @param endExclusive 终止下标(不包含)
     */
    private void quickSort(int[] arr, int startInclusive, int endExclusive) {
        if (startInclusive < endExclusive) {
            int pivotIndex = layDownPivot(arr, startInclusive, endExclusive);
            quickSort(arr, startInclusive, pivotIndex);
            quickSort(arr, pivotIndex + 1, endExclusive);
        }
    }

    /**
     * 将最后一个元素视作枢轴元素，找到第一个大于枢轴元素的元素及其下标index，如果右侧没有更小的元素，则index就是枢轴最终的下标。
     * 遍历index右侧的元素，更小的元素与index交换，index也右移，表示更小元素移到枢轴元素右侧。
     * @param arr 排序数组
     * @param startInclusive 起始下标(包含)
     * @param endExclusive 终止下标(不包含)
     */
    private int layDownPivot(int[] arr, int startInclusive, int endExclusive) {
        int pivot = arr[endExclusive - 1]; // 枢轴元素
        // 找到首个大于枢轴的元素下标
        int p = findFirstBigger(arr, startInclusive, endExclusive, pivot);
        if (p == -1) { // 此时表示枢轴元素已经在最终位置，可以返回了
            return endExclusive - 1;
        }
        int pointer = p++; // 若右侧没有更小的元素，则pointer就是枢轴最终的下标
        // 遍历剩余的元素，若找到小于枢轴的元素，将其与 pointer 交换，并让 pointer++
        while (p < endExclusive) {
            if (arr[p] < pivot) {
                swap(arr, p, pointer);
                pointer++;
            }
            p++;
        }
        // 让枢轴元素前往指定位置
        swap(arr, pointer, endExclusive - 1);
        return pointer;
    }

    /**
     * 找到首个大于枢轴的元素下标
     */
    private int findFirstBigger(int[] arr, int startInclusive, int endExclusive, int pivot) {
        for (int i = startInclusive; i < endExclusive; i++) {
            if (arr[i] > pivot) {
                return i;
            }
        }
        return -1;
    }
}
